|
In formal language theory, a grammar is noncontracting (or monotonic) if all of its production rules are of the form α → β where α and β are strings of nonterminal and terminal symbols, and the length of α is less than or equal to that of β, |α| ≤ |β|, that is β is not shorter than α. A grammar is essentially noncontracting if there may be one exception, namely, a rule ''S'' → ε where ''S'' is the start symbol and ε the empty string, and furthermore, ''S'' never occurs in the right-hand side of any rule. None of the rules of a noncontracting grammar decreases the length of the string that is being rewritten. If each rule even properly increases the length, the grammar is called a growing context-sensitive grammar. == History == Chomsky (1963) called a noncontracting grammar a type 1 grammar; in the same work, he called a context-sensitive grammar a "type 2 grammar", and he proved that these two are weakly equivalent (context-free grammars were designated "type 4" in this work).〔Chomsky, N. 1963. Formal properties of grammar. Handbook of Mathematical Psychology. R.D. Luce, R.R. Bush, & E. Galanter (eds), New York: Wiley. pp. 360-363 and 367〕 The type numbering scheme in this 1963 work of Chomsky does not coincide with the earlier one known today as the Chomsky hierarchy because he was trying to emphasize the distinction between weak () and strong () equivalence; in his 1959 work he had used "type 1 grammar" to denote a context-sensitive grammar and "type 2" for context-free.〔Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67. (141-42 for the definitions)〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Noncontracting grammar」の詳細全文を読む スポンサード リンク
|